50. Pow(x, n)

思路

递归，分治。

对于一个 x 的 n 次方：

• 如果 n 小于 0，x 的 n 次方等于 $\frac{1}{x}$ 的 -n 次方
• 如果 n 是一个偶数，x 的 n 次方等于 $x\ast x$ 乘以 $\frac{n}{2}$ 次方
• 如果 n 是一个奇数，x 的 n 次方等于 x 乘以 x 的 n-1 次方
• 如果 n 等于 0，直接返回 1

代码实现

/**
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
var myPow = function (x, n) {
  // n=0 直接返回 1
  if (n === 0) return 1

  // n<0 时 x 的 n 次方等于 1 除以 x 的 -n 次方分
  if (n < 0) return 1 / myPow(x, -n)

  // n 是奇数时 x 的 n 次方 = x*x 的 n-1 次方
  if (n % 2) return x * myPow(x, n - 1)

  // n 是偶数，使用分治，一分为二，等于 x*x 的 n/2 次方
  return myPow(x * x, n / 2)
}